package lc.q1_50;

import java.util.Arrays;

public class Q05 {

    public String longestPalindrome2(String s) {
        // 中心扩展法，从中间往左右扩展，直到最好
        int n = s.length();
        int maxLength = 1;
        String result = s.substring(0, 1);
        for (int i = 0; i < n; i++) {
            // 两种扩展，第一种以当前位置，第二种
            int c1 = center(s, i , i);
            int c2 = center(s, i, i + 1);
            int max = Integer.max(c1, c2);
            if (max > maxLength) {
                maxLength = max;
                // 如果是偶数，说明是c2，此时的一半包含了本身的值，所以需要-1
                result = s.substring(i - (max - 1) / 2, i + max / 2 + 1);
            }
        }
        return result;
    }

    private int center(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left --;
            right ++;
        }
        return right - left - 1;
    }

    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        // 全部填充为true
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], true);
        }
        // 从后往前
        int maxLength = 1;
        String result = s.substring(0, 1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // 判断(i,j)是否为回文
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    result = s.substring(i, j + 1);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Q05 q05 = new Q05();
        System.out.println(q05.longestPalindrome2("babad"));
    }
}
